import random
from typing import List


class TreeNode:
    def __init__(self, value: int):
        self.value = value
        self.lazy = 0
        self.left = None
        self.right = None


class DynamicSegmentTree:

    def __init__(self, nums: List[int]):
        self.root = TreeNode(sum(nums))
        self.nums = nums


    def push_up(self, cur_node: TreeNode):
        cur_node.value = cur_node.right.value + cur_node.left.value

    def push_down(self, left: int, right: int, cur_node: TreeNode):
        mid = (left + right) // 2
        if cur_node.left is None:
            cur_node.left = TreeNode(sum(self.nums[left:mid + 1]))
        if cur_node.right is None:
            cur_node.right = TreeNode(sum(self.nums[mid + 1:right + 1]))
        if cur_node.lazy != 0:
            cur_node.left.value += (mid - left + 1) * cur_node.lazy
            cur_node.left.lazy += cur_node.lazy
            cur_node.right.value += (right - mid) * cur_node.lazy
            cur_node.right.lazy += cur_node.lazy
            cur_node.lazy = 0

    # 区间查询
    def query_range(self, num_left: int, num_right: int, left: int, right: int, cur_node: TreeNode):
        if num_left <= left and right <= num_right:
            return cur_node.value

        mid = (left + right) // 2
        res = 0
        self.push_down(left, right, cur_node)
        if num_left <= mid:
            res += self.query_range(num_left, num_right, left, mid, cur_node.left)
        if num_right > mid:
            res += self.query_range(num_left, num_right, mid + 1, right, cur_node.right)
        return res

    # 区间增加
    def range_add(self, value: int, num_left: int, num_right: int, left: int, right: int, cur_node: TreeNode):
        if num_left <= left and right <= num_right:
            cur_node.value += (right - left + 1) * value
            if left != right:
                cur_node.lazy += value
            return
        self.push_down(left, right, cur_node)
        mid = (left + right) // 2
        if num_left <= mid:
            self.range_add(value, num_left, num_right, left, mid, cur_node.left)
        if mid < num_right:
            self.range_add(value, num_left, num_right, mid + 1, right, cur_node.right)
        self.push_up(cur_node)

if __name__ == '__main__':
    n = 1000
    nums = [0] * n
    total = [0] * (n + 1)
    for i in range(n):
        nums[i] = random.randint(0, 10000000)
        total[i + 1] = total[i] + nums[i]

    lazySegmentTree = DynamicSegmentTree(nums)
    for i in range(n):
        left = random.randint(0, n - 1)
        right = random.randint(left, n - 1)
        pre_value = lazySegmentTree.query_range(left, right, 0, n - 1, lazySegmentTree.root)
        # print(pre_value == total[right + 1] - total[left])
        lazySegmentTree.range_add(17, left, right, 0, n - 1, lazySegmentTree.root)
        new_value = lazySegmentTree.query_range(left, right, 0, n - 1, lazySegmentTree.root)
        correct_value = pre_value + 17 * (right - left + 1)
        print('{}:{} = {}'.format(pre_value, new_value, correct_value == new_value))
        print('{}:{}'.format(right - left + 1, correct_value - new_value))
